The present invention relates to telecommunications networks, and more particularly to packet forwarding.
FIG. 1 illustrates a telecommunications network, e.g. the Internet or a network used by a company or government organization. Routers 110.A, 110.B, . . . forward packets 114 between end-point nodes 120 (including 120A, 120B, etc.) and/or networks 130 comprising such nodes. The packets are transmitted over network links 140. Each router 110 may or may not be an end-point node, and each network 130 may include other routers 110 and nodes 120.
A router 110 forwards each packet based on the packet's address D_Addr and possibly other information, e.g. the incoming link 140 (the link on which the packet arrived). To enable packet forwarding, routers 110 exchange information on network topology to determine paths to nodes 120 and networks 130. For example, if a router F (i.e. 110.F) receives a packet from a node 120B, and the packet's destination address D_Addr identifies the node 120C, then the packet can be forwarded through routers 110.C and 110.D or, alternatively, through routers 110.A, 110.B, 110.D. The router 110.F makes the forwarding decision based on the costs of the two paths. The “cost” can be defined in many ways, and may take into account delays, bandwidths, and reliability of links 140 in each path. According to many routing algorithms, router F selects the shortest path, i.e. the path having the minimal cost. This is called minimal routing, and it is used in many routing protocols, e.g. RIP (Routing Information Protocol), OSPF (Open Shortest Path First), ISIS (Intermediate System to Intermediate System), and BGP (Border Gateway Protocol).
Minimal routing reduces delays and improves other parameters of interest (depending on how the cost is defined). In addition, minimal routing helps eliminate loops in packet forwarding. The loops are eliminated because on each hop of the shortest path, the packet moves closer to the destination (i.e. the cost to the destination decreases on each hop), and this means that the packet cannot return to a previous hop. In contrast, in non-minimal routing, loops are more difficult to avoid, but non-minimal routing increases the path diversity (the number of paths between given network nodes), and thus may increase the network utilization and bandwidth, relieve congestion, and improve reliability in case of failure.
An example of non-minimal routing is found in EIGRP (Extended Interior Gateway Routing Protocol). Suppose a router A (FIG. 2) receives a packet 114 with a destination address D_Addr corresponding to a network 130.N. Router A can reach network 130.N via router B or router C. Suppose that the cost of each path is the sum of the costs of the links. Exemplary costs are shown next to the links; for example, the link “AC” between routers A and C has the cost of 10, the link “AB” between A and B has the cost of 7, etc. (The links are assumed bidirectional in this example, with the same cost in each direction.) The costs of the paths from router A to network 130.N are as follows:
path A-B-D-N (from A to B, then to D, then to network 130.N) has the cost of 7+11+1=19;
path A-C-D-N has the cost of 10+10+1=21;
path A-C-B-D-N has the cost of 10+15+11+1=37;
path A-B-C-D-N has the cost of 7+15+10+1=33.
The shortest path is A-B-D-N.
Router A therefore configures itself to forward the packets addressed to network 130.N on link AB. If link AB fails, then path A-C-D-N becomes the shortest, and router A starts forwarding the packets on link AC.
EIGRP also provides non-minimal routing when there is no failure: router A can be configured to use both links AB and AC even when there is no failure. If so configured (by an administrator), router A will proportion the traffic based on the costs: most packets to network 130 will be forwarded on link AB, but some of the packets will be forwarded on the non-minimal path on link AC.
The danger is that if a packet is forwarded to router C (on link AC), and router C uses non-minimal forwarding, then router C may return the packet back to router A, and the packet may circulate between A and C indefinitely without reaching the destination. To prevent such looping, EIGRP allows a router to use a non-minimal path only if the next hop on the path is closer to the destination than the router itself. In FIG. 2, router C is closer to network 130.N (at the shortest distance of 10+1=11) than router A (shortest distance is 7+11+1=19), and therefore A can forward the packets to C for network 130.N. However, C cannot forward such packets to A because A is farther from destination 130.N than C. In fact, C cannot use any non-minimal path to the destination 130.N through router A or B because routers A and B are farther from network 130.N than C.
In FIG. 3, the cost of the CD link is increased to 20, and therefore router A cannot perform non-minimal forwarding because now router C is farther away from network 130.N than router A.